class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    vector<int> solve(vector<int>& a) {
        int n = a.size();
        stack<int> st;
        vector<int> v;
        vector<int> right(n, 0);
        right[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) right[i] = max(a[i], right[i + 1]);
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == n) {
                j = i;
                v.push_back(a[i]);
                break;
            }
            st.push(a[i]);
        }
        for (int i = j + 1; i < n; i++) {
            while (st.size() && st.top() > right[i]) {
                v.push_back(st.top());
                st.pop();
            }
            st.push(a[i]);
        }
        while (st.size()) {
            v.push_back(st.top());
            st.pop();
        }
        return v;
    }
};